from 翻译包 import *
import random
from mytools import *

class CountMinBound:
	def __init__(self, 深度, 宽度):
		self.深度 = 深度
		self.宽度 = 宽度

		self.过滤器 = []
		for 计数 in 范围(宽度*深度):
			self.过滤器.append([0, 0, 0])

		self.随机因子 = []
		random.seed(0)
		for 计数 in 范围(深度):
			self.随机因子.append(random.randint(0, 0xffffffff))

	def 更新(self, 数据包):
		标识符 = 数据包
		指纹 = hash1(标识符.encode("utf-8"))&0xffff
		结果 = 0xffffffff

		for 序号 in 范围(self.深度):
			索引 = (hash1(标识符.encode("utf-8"))^self.随机因子[序号])%self.宽度+序号*self.宽度
			if 指纹 == self.过滤器[索引][0]:
				self.过滤器[索引][1] += 1
				if self.过滤器[索引][2] < 结果:
					self.过滤器[索引][2] += 1
					结果 = self.过滤器[索引][2]
			elif 0 == self.过滤器[索引][1]:
				self.过滤器[索引][0] = 指纹
				self.过滤器[索引][1] += 1
				if self.过滤器[索引][2] < 结果:
					self.过滤器[索引][2] += 1
					结果 = self.过滤器[索引][2]
			else:
				self.过滤器[索引][1] -= 1
				if self.过滤器[索引][2] < 结果:
					结果 = self.过滤器[索引][2]

		return 结果

	def 查询(self, 数据包):
		标识符 = 数据包
		指纹 = hash1(标识符.encode("utf-8"))&0xffff
		结果 = 0xffffffff

		for 序号 in 范围(self.深度):
			索引 = (hash1(标识符.encode("utf-8"))^self.随机因子[序号])%self.宽度+序号*self.宽度
			if self.过滤器[索引][2] < 结果:
				结果 = self.过滤器[索引][2]

		return 结果
